/**
 * 题目: 寻找两个正序数组的中位数
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 *
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 */

/**
 * 该题的难点在于时间复杂度要在 O(log(m + n))内, 普通无脑遍历会超时
 *
 * 1. 可以用两个优先级队列, 一个大根堆, 一个小根堆, 两个堆中存放相同
 * 数量的元素, 只要求得大根堆和小根堆的栈顶元素的就是所要求的中位数,
 * 有个小细节, 就是我们要使得小根堆的元素数量不小于大根堆, 这样要求的
 * 中位数不论是单独一个数还是两个数的平均数, 都课可以得到
 * 时间复杂度 O(m + n)   空间复杂度 O(m + n)  会超时
 *
 * 2. 要求在 O(log(m + n)) 的时间复杂度里完成, 第一印象联想到的应该是二分查找,
 * 但还有一种寻找第 k小的方法, 每次寻找都将第 k小之前的数给删掉, 直到可以去到第 k小的元素
 * 时间复杂度 O(log(k)) == O(log(m + n))  空间复杂度 O(1) (因为反复压栈)
 *
 * 3. 理解中位数的定义, 和方法一差不多的思路, 只不过是此方法没有用堆, 而是直接开始分割数组,
 * 将数组分为两个等长的部分(当总长为偶数时), 此时只要返回左边最大值和右边最小值的平均值即为中位数
 * 或者将数组分为左边长度比右边长度多一(当总长为奇数时), 此时只要返回左边的最大值即为中位数
 * 时间复杂度 O( log(min(m , n) ))  空间复杂度 O()
 */

public class Main {
    public static void main(String[] args) {
        int[] nums1 = {1, 3};
        int[] nums2 = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
        System.out.println(new Main().findMedianSortedArrays(nums1, nums2));
    }

    // 方法二: 删除数组的 k - 1 个元素
    // !!!!!! 有问题多调试
    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;

        // 所要求的第 k小的数
        // 为了奇数和偶数统一处理, 细节处理下left, right
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;

        //统一处理奇数和偶数
        return (getKnum(nums1, 0, m - 1, nums2, 0, n - 1, left) +
                getKnum(nums1, 0, m - 1, nums2, 0, n - 1, right)) * 0.5;
    }
    private int getKnum(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        //!!!!!!!! 细节 + 1 .... !!!!!!
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;

        // 保证len1 < len2, 这样如果有一个数组被排光, 一定为 nums1 (交换两个数组的顺序就好)
        if (len1 > len2) return getKnum(nums2, start2, end2, nums1, start1, end1, k);

        // 当 nums被排光后, 直接返回 nums2中的第 k小数就好, 注意下标的映射, 所求的是第 k小, 所以要减一
        // !!!!!!!!!
        // 注意: 这里只需要 == 0就好了 不需要写 <= 0, 因为就算后面取得是 len1, start1 = end1 + 1,
        // 最后去 len1 = end1 - start1 + 1 = 0, 正好可以走 len1 == 0, 反而 start1 = end1时, 最后 len1会等于1, 导致失败
        if (len1 == 0) return nums2[start2 + k - 1];

        // 递归出口
        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        // 要是排除后, 各个数组应该从哪里开始继续排
        // 注意: 因为是要求第 k小, 所以下标映射要 -1
        // 但若果排的数直接大于数组长度, 直接排净就好了, 然后会从, len1 == 0, 这里返回
        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        // 比较i, j元素的大小
        if (nums1[i] > nums2[j]) {

            // 排的是 nums2的元素
            // 要减去已经排除的元素
            k -= j - start2 + 1;

            // 下标映射要从 j + 1开始, 因为前面的元素已经被排除, 第 j个元素也已经被排除, 所以要 +1
            return getKnum(nums1, start1, end1, nums2, j + 1, end2, k);

        } else {

            // 排的是 nums1的元素
            k -= i - start1 + 1;
            return getKnum(nums1, i + 1, end1, nums2, start2, end2, k);
        }
    }

    //*******************************************************************
    // 方法三 : 将数组等分
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;

        // 保证 m <= n, 减少接下来二分查找的复杂度
        if (m > n) return findMedianSortedArrays(nums2, nums1);

        // 定义 nums1的可分割点
        int iMin = 0, iMax = m;

        // 配置下标映射问题
        // i将 nums1分为两半, j将 nums2分为两半
        // 其实 j 可以取 n 的一半的, 但是因为要和 i关联起来, 所以强行加上 i,
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            // m + n + 1是总分割点数
            // 减去 i 就是 nums2的分割点
            int j = (m + n + 1) / 2 - i;

            // 我们要保证左边部分的最大值要小于等于右边部分的最小值,
            // 也就是 max(nums1[i - 1], nums2[j - 1]) <= min(nums1[i], nums2[j])
            // 又因为nums[i - 1]本身就小于nums[i], nums2[j - 1]本身就小于 nums[j]
            // 所以只要满足 nums2[j - 1] <= nums1[i] 和 nums1[i - 1] <= nums2[j]
            // 当不满足时, 要将次个不满足的元素和对方部分互换, 又因为他们处于上下两个不同的数组,
            // j 又和 i有关系, 只要 i变大, j自然就会变小, 反之也是如此
            // 所以只要将 i++ 或者i--, 就可以实现互换元素
            // 这里可以用 + 1 或者 - 1, 只要保证下标不越界就好了

            if (j != 0 && i != m && nums1[i] < nums2[j - 1]) {
                // 当 i需要++时
                // 注意下边的越界, 因为用的是 - 1, 所以要保证 j != 0 && i != m
                // 还要保证 nums1数组右边部分的最小值要 小于 nums2左边的最大值
                iMin = i + 1;
            } else if (i != 0 && j != n && nums1[i - 1] > nums2[j]) {
                // 当 i需要--时
                // 要保证 nums1左边的最大值要 小于 nums2右边的最小值
                iMax = i - 1;
            } else {
                int maxLeft  = 0, minRight = 0;

                // 如果 i == 0时, 说明nums1的数据全在右边, 直接取 nums2的值就好了
                if (i == 0) maxLeft = nums2[j - 1];
                    // 如果 j == 0时, 说明nums2的数据全在右边, 直接取 nums1的值就好了
                else if (j == 0) maxLeft = nums1[i - 1];
                else {
                    //都不满足
                    maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                }

                // 如果总长度为奇数, 直接返回左边的最大值就可以了
                if ((m + n) % 2 == 1) return maxLeft;
                else {
                    // 如果是偶数就要考虑两部分
                    if (i == m) minRight = nums2[j];
                    else if (j == n) minRight = nums1[i];
                    else {
                        minRight = Math.min(nums1[i], nums2[j]);
                    }
                    return (minRight + maxLeft) * 0.5;
                }
            }
        }
        return 0.0;
    }
}
